The invention relates to a method for distributing computation time in a computer system
The method according to the invention can be applied, in particular, to computer systems which process a number of tasks in the form of competing subprocesses or “threads”. In this context, an activity or a program which is being executed is denoted as a “thread”. Also in common use for this are the terms of “task” or “process”; however, depending on context, these also implicitly include assumptions relating to further properties such as, for example, the address space in which the program is running. These further properties are, however, of no importance for the present invention.
An allocation process which is usually designated as a “scheduler” determines which thread comes to be executed, and when, that is to say which thread is allocated computation time or a processor. The scheduler is thus an algorithm which decides which thread comes to be executed, and when.
In such a computer system in which a number of mutually independent tasks can be processed in the form of threads, a thread can assume various states:
Computing: the thread has a computation time requirement and is being executed, that is to say it has been allocated a processor.
Willing to compute: the thread is ready for execution and therefore has a computation time requirement and is waiting for a processor to be allocated to it.
Blocked: the thread is not ready for execution and is waiting for an external event.
A thread goes over actively from the computing state into the blocked state by calling up the operating system as appropriate. The change from blocked to willing to compute happens through the onset of the external event, or the prompting of another thread, which undertakes an appropriate system call-up to this end. So that a thread willing to compute can become computing, the scheduler needs to allocate it one of the available processors. Whenever a thread changes either                from the computing state into the blocked state, or        from the blocked state into the willing to compute state,        the scheduler is called up in order either to allocate the processor becoming free a new process ready for computation, or to withdraw the processor from one of the computing threads if the thread becoming willing to compute is classified as more important.        
From the point of view of the scheduler, there are a number of threads willing to compute which are competing for the allocation of a processor. It is assumed that the number of available processors is generally smaller than the number of threads ready for computation, that is to say the scheduler normally finds more “competitors” for a processor than there are processors to be awarded.
A multiplicity of procedures are known as to how a scheduler can be used to fix the thread to which a processor is allocated at a respective point in time.
In the case of a first method, which is known as priority method, priorities are assigned to the individual threads. A thread of relatively high priority obtains preference over a thread of relatively low priority. Depending on requirement, threads of the same priority are either not admissible, or they are placed in a queue in the sequence in which they become willing to compute. Depending on requirements, the priority of the individual threads can both be statistically fixed and be dynamically determined and be continuously corrected.
In the case of the priority method, there is no possibility of guaranteeing a thread a computation time allocation: threads having a high priority can occupy the processors as long as desired, and it can happen in the extreme case that threads having a low priority never become computing.
In a further method, which is also known as time slice method (round robin), the period of time for which a thread may use a processor is limited. As soon as a thread currently operating has used the processor allocated to it for more than a fixed duration (that is to say it has “consumed” its “time slice”), it is necessarily interrupted. In this case, the thread remains willing to compute, and is placed at the end of a queue. Depending on requirements, the duration of the time slice can be a constant or a thread-specific variable. This method requires an external timer which activates the operating system via an interrupt at specific time intervals so that said operating system can monitor the time consumed by the running thread and, if appropriate, can activate the scheduler.
The time slice method enables the allocation of computation time, but it does not permit a rapid reaction to external events: in the most unfavorable case, a thread which becomes willing to compute on the basis of an interrupt, for example, must wait for the entire cycle, that is to say the time slices of all the other threads willing to compute, before it can become computing.
In many computer systems, in particular in computer systems having a number of threads of which some are subject to real time requirements, however, at least these “real time threads” must be able to react to external events within a maximum time which is guaranteed and, ideally, as short as possible, that is to say they must be able to become computing. At the same time, threads exist which require a minimum allocation of computation time in order to accomplish their respective activities. It must also be possible to guarantee such a time allocation for threads. Combinations of the above-named methods are correspondingly known.
In a method known from EP-A2-0658 841 groups of threads are assigned priorities, and the individual threads are allocated computation time inside the groups in a time slice method.
In a further method, known from EP-A2-880 059, the threads are grouped into classes which are arranged in a hierarchy. Each class has a time function value which determines when the class is allocated computation time. Within a level of the hierarchy, computation time priorities are defined by one or more time-based functions which can be constant or change dynamically.